State space planning

Contents

Definition

The simplest classical planning(see Automated_planning) algorithms are state space search algorithms. These are search algorithms in which the search space is a subset of the state space: Each node corresponds to a state of the world, each arc corresponds to a state transition, and the current plan corresponds to the current path in the search space. Forward Search and Backward Search are two of main samples of state space planning.

Forward Search

Forward search is an algorithm that searches forward from the initial state of the world to try to find a state that satisfies the goal formula.

Forward-search(O, s0, g)

 s = S0
 P = the empty plan
 loop
     if s satisfies g then return P
     applicable = {a | a is a ground instance of an operator in O,and precond(a) is true in s}
     if applicable = ∅ then return failure 
     nondeterministically choose an action a from applicable
 s = γ(s,a)
 P = P.a

Backward Search

Backward-search(O, s0, g)

 P = the empty plan
 loop
     if s0 satisfies g then return P
     relevant = {a |a is a ground instance of an operator in O that is relevant for g}
     if relevant = ∅ then return failure 
     nondeterministically choose an action a from relevant
 P = a.P  
 s = γ-1(s,a)

References